# 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
#
#  算法的时间复杂度应该为 O(log (m+n)) 。
#
#
#
#  示例 1：
#
#
# 输入：nums1 = [1,3], nums2 = [2]
# 输出：2.00000
# 解释：合并数组 = [1,2,3] ，中位数 2
#
#
#  示例 2：
#
#
# 输入：nums1 = [1,2], nums2 = [3,4]
# 输出：2.50000
# 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
#
#
#  示例 3：
#
#
# 输入：nums1 = [0,0], nums2 = [0,0]
# 输出：0.00000
#
#
#  示例 4：
#
#
# 输入：nums1 = [], nums2 = [1]
# 输出：1.00000
#
#
#  示例 5：
#
#
# 输入：nums1 = [2], nums2 = []
# 输出：2.00000
#
#
#
#
#  提示：
#
#
#  nums1.length == m
#  nums2.length == n
#  0 <= m <= 1000
#  0 <= n <= 1000
#  1 <= m + n <= 2000
#  -10⁶ <= nums1[i], nums2[i] <= 10⁶
#
#  Related Topics 数组 二分查找 分治 👍 4749 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        len1, len2 = len(nums1), len(nums2)

        def get_k(k):
            idx1, idx2 = 0, 0
            while True:
                if idx1 == len1:
                    return nums2[idx2 + k - 1]
                if idx2 == len2:
                    return nums1[idx1 + k - 1]
                if k == 1:
                    return min(nums1[idx1], nums2[idx2])
                t_idx1 = min(idx1 + k // 2 - 1, len1 - 1)
                t_idx2 = min(idx2 + k // 2 - 1, len2 - 1)
                if nums1[t_idx1] <= nums2[t_idx2]:
                    k -= t_idx1 - idx1 + 1
                    idx1 = t_idx1 + 1
                else:
                    k -= t_idx2 - idx2 + 1
                    idx2 = t_idx2 + 1

        total_len = len1 + len2
        if total_len % 2 == 1:
            return get_k((total_len + 1) // 2)
        else:
            return (get_k(total_len // 2) + get_k(total_len // 2 + 1)) / 2


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


"""
目标: 找总数组中的第k个小的元素, 二分法取 k/2
----
中位数定义: (奇数: (m+n)/2, 偶数: ((m+n)/2, 和 (m+n)/2 + 1)的平均值)
----
二分法: 
A, B 分别取 k/ 2 的数比较, 数组小的部分丢掉, k更新未剩余的k值
剩余1个k, 取小的值(中位数小的值排在前面)
一个数组为空时, 取另一个数组的中位数
----
证明: 
A, B 分别取 k/2个数, k/2之前分别有k/2-1个数
对于小的数, 最多时的大小关系: A(k/2-1) + B(k/2-1) A[k/2] B[K/2]
即最多有k-2个数小于 A[k/2], 即 A[k/2]一定不是第k个小的数, 舍弃这部分A, 更新起始位置
k更新为剩余的数, 
----
tips:
开始坐标:i, 第 x 个数: num[i+x-1]
结束坐标:end, 开始坐标:start, 一共有几个数: end-start+1 
奇数中间的数: nums[(len + 1) // 2]
偶数中间的数: (nums[len // 2] + nums[len //2 + 1] )/ 2
"""
# def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
#     len1 = len(nums1)
#     len2 = len(nums2)
#
#     def get_k(k):
#         idx1, idx2 = 0, 0
#         while True:
#             if idx1 == len1:
#                 return nums2[idx2 + k - 1]
#             if idx2 == len2:
#                 return nums1[idx1 + k - 1]
#             if k == 1:
#                 return min(nums1[idx1], nums2[idx2])
#             t_idx1 = min(idx1 + k // 2 - 1, len1 - 1)
#             t_idx2 = min(idx2 + k // 2 - 1, len2 - 1)
#             n1, n2 = nums1[t_idx1], nums2[t_idx2]
#             if n1 <= n2:
#                 k -= t_idx1 - idx1 + 1
#                 idx1 = t_idx1 + 1
#             else:
#                 k -= t_idx2 - idx2 + 1
#                 idx2 = t_idx2 + 1
#
#     total_len = len1 + len2
#     if total_len % 2 == 1:
#         return get_k((total_len + 1) // 2)
#     else:
#         return (get_k(total_len // 2) + get_k((total_len // 2 + 1))) / 2

if __name__ == '__main__':
    s = Solution()
    r1 = s.findMedianSortedArrays([1, 3], [2])
    assert r1 == 2, r1
    r2 = s.findMedianSortedArrays([1, 2], [3, 4])
    assert r2 == 2.5, r2
    r3 = s.findMedianSortedArrays([], [1])
    assert r3 == 1, r3
    r4 = s.findMedianSortedArrays([1], [2, 3, 4, 5, 6])
    assert r4 == 3.5, r4
